package com.demo.datastructure.reorder.mergeSort;

import com.demo.datastructure.reorder.Example;

/**
 * @author ljr
 * @version 1.0
 * @description: 自底向上的原地归并排序
 * @date 2021/9/18 20:31
 */
public class SimpleMergeSort2 implements Example {

    @Override
    public void sort(Comparable[] a, int low, int high) {
        int n = a.length;
        for(int sz = 1; sz < n; sz += sz){
            for(int lo = 0;  lo < n - sz; lo += sz+sz)
                merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, n-1));
        }
    }

    private void merge(Comparable[] a, int low, int mid, int high) {
        int length = high-low+1;
        Comparable[] newA = new Comparable[length];

        int l = low, h = mid+1;
        for(int i = 0; i < length; i++){
            if(l > mid)  newA[i] = a[h++];
            else if(h > high)  newA[i] = a[l++];
            else if(less(a[l], a[h])) newA[i] = a[l++];
            else newA[i] = a[h++];
        }

        for(int i = 0; i < length; i++){
            a[low++] = newA[i];
        }
    }


    private void merge3(Comparable[] a, int low, int mid, int high) {
        int i =  low, j = mid+1;
        Comparable[] aux = new Comparable[high+1];
        for(int k = low; k <= high; k++)
            aux[k] = a[k];

        for(int k = low; k <= high; k++){
            if(i > mid) a[k] = aux[j++];
            else if(j > high) a[k] = aux[i++];
            else if(less(aux[j], aux[i])) a[k] = aux[j++];
            else a[k] = aux[i++];
        }
    }
}

